module Queue.SchedQueue (Queue,
                       isEmpty,
                       empty,
                       add,
                       head,
                       tail) where

import Prelude hiding (head, tail)

-- Invariante:
-- length left = length sched + length right

data Queue a = Queue{left::[a], lenLeft::Int, sched::[a], lenSched::Int, right::[a], lenRight::Int}

isEmpty Queue{left=[]} = True
isEmpty _ = False

empty = Queue [] 0 [] 0 [] 0

add q@Queue{right=xs,lenRight=lr} x = norm q{right=x:xs,lenRight=lr+1}

head Queue{left=x:_} = x
head Queue{left=[]} = error "head on empty queue"

tail q@Queue{left=_:xs,lenLeft=ll} = norm q{left=xs,lenLeft=ll-1}
tail Queue{left=[]} = error "tail on empty queue"

--norm q@Queue{left=xs,lenLeft=ll,right=ys,lenRight=lr} =
--  if lr > ll then
--    Queue (xs++reverse ys) (ll+lr) [] 0
--  else q
norm q@Queue{sched=[]} = 
        let 
            (l, ll) = rotate q
        in
            Queue l ll l ll [] 0
            
norm q@Queue{sched=s:ss} = q{sched=ss}

rotate Queue{left=[], right=r:rs, sched=s, lenSched=ls} = 
        (r:s, ls+1)
rotate q@Queue{left=l:ls, right=r:rs, lenRight=lr, lenSched=lens, lenLeft=ll, sched=s} = 
        let
            (list, length) = rotate (Queue ls (ll-1) (r:s) (lens+1) rs (lr-1))
        in
            (l:list, length+1)